Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?
In [1]:
from sympy import sieve
import numpy as np
N = 12000
mu = np.ones(N+1, dtype=int16)
for p in sieve.primerange(1, N+1):
for k in range(p, N+1, p):
mu[k] *= -1
pp = p*p
for k in range(pp, N+1, pp):
mu[k] = 0
g = lambda n: int((n-2.0)**2/12+0.5)
print sum(mu[d] * g(N/d) for d in xrange(1, 10000))
Discussion:
Let $g(n)$ denote the number of pairs of positive integers $(x,y)$ such that $y \le n$ and $\frac13 < \frac{x}{y} < \frac{1}{2}$. Let $f(n)$ denote the number of pairs with the above properties and the additional condition that $x$ and $y$ are relatively prime. Then $$g(n) = \sum_{k=1}^n f(n/k).$$ By the Mobius inversion formula, $$f(n) = \sum_{k=1}^n \mu(k) g(n/k).$$ It can be shown that if $n$ is an integer, $g(n)$ is the integer nearest to $\frac1{12} (n-2)^2$.
Putting this information together gives an efficient algorithm for calculating $f(n)$.
In [ ]: